package com.shangxia.leetcode.hoot100.easy;

import lombok.extern.slf4j.Slf4j;

/**
 * @ProjectName: leetcode
 * @ClassName: ClimbStairs70
 * @Time: 2020/11/30
 * @Author: zhouy
 * @Description:
 * @Experience:
 */

@Slf4j
public class ClimbStairs70 {
    public static void main(String[] args) {
        Long start = System.currentTimeMillis();
        System.out.println(climbStairs(45));
//        System.out.println(climbStairs2(45));
        System.out.println(System.currentTimeMillis()-start);
    }

    public static int climbStairs(int n) {
        switch (n){
            case 0:
                return 0;
            case 1:
                return 1;
            case 2:
                return 2;
            default:
                return climbStairs(n-1)+ climbStairs(n-2);
        }
    }
    public static int climbStairs2(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }

}
